home *** CD-ROM | disk | FTP | other *** search
/ Ham Radio 2000 #1 / Ham Radio 2000.iso / ham2000 / tcp_ip / wnos / wn941101 / lzw.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-10  |  15.1 KB  |  586 lines
  1. /*        SM0RGV data compression routines.
  2.  * This file implements the Lempel-Ziv Welch (LZW) data compression
  3.  * algorithm but with a variable code size, as in GIF format files.
  4.  *
  5.  * Copyright 1990 by Anders Klemets, SM0RGV.
  6.  * Permission granted for non-commercial distribution only.
  7.  */
  8.  
  9. #include "global.h"
  10. #include "config.h"
  11. #ifdef LZW
  12. #include "mbuf.h"
  13. #include "proc.h"
  14. #include "lzw.h"
  15. #include "usock.h"
  16. #include "session.h"
  17. #include "cmdparse.h"
  18. #include <ctype.h>
  19.  
  20. static void near fastencode __ARGS((struct usock *up,char data));
  21. static void near morebits __ARGS((struct lzw *lzw));
  22. static void near cleartbl __ARGS((struct lzw *lzw));
  23. static void near addtobuffer __ARGS((struct usock *up,int32 code));
  24. static void near decodetbl __ARGS((int32 code,struct lzw *lzw));
  25. static int32 near nextcode __ARGS((struct usock *up));
  26.  
  27. int
  28. dolzw(argc,argv,p)
  29. int argc;
  30. char *argv[];
  31. void *p;
  32. {
  33.     if(argc > 1) {
  34.         switch(tolower(*argv[1])) {
  35.         case 'm':
  36.             if(argc == 2) {
  37.                 tprintf("LZW mode: %s\n",Lzwmode ? "fast" : "compact");
  38.             } else {
  39.                 switch(tolower(*argv[2])) {
  40.                 case 'f':
  41.                     Lzwmode = LZWFAST;
  42.                     break;
  43.                 case 'c':
  44.                     Lzwmode = LZWCOMPACT;
  45.                     break;
  46.                 default:
  47.                     tputs("Usage: lzw mode <fast|compact>\n");
  48.                     return -1;
  49.                 }
  50.             }
  51.             return 0;
  52.         case 'b':
  53.             return setintrc(&Lzwbits,"LZW bits",--argc,++argv,9,16);
  54. /*
  55.         case '=':
  56.             if(argc == 3) {
  57.                 struct session *sp;
  58.                 if((sp = sessptr(argv[2])) != NULLSESSION) {
  59.                     lzwinit(sp->s,Lzwbits,Lzwmode);
  60.                 }
  61.             }
  62.             return 0;
  63. */
  64.         }
  65.     }
  66.     return -1;
  67. }
  68.  
  69. /* Initialize a socket for compression. Bits specifies the maximum number
  70.  * of bits per codeword. The input and output code tables might grow to
  71.  * about (2^bits * 3) bytes each. The bits parameter does only serve as a
  72.  * recommendation for the decoding, the actual number of bits may be
  73.  * larger, but not never more than 16.
  74.  */
  75. void
  76. lzwinit(s,bits,mode)
  77. int s;        /* socket to operate on */
  78. int bits;    /* maximum number of bits per codeword */
  79. int mode;    /* compression mode, LZWCOMPACT or LZWFAST */
  80. {
  81.     struct usock *up;
  82.  
  83.     if((up = itop(s)) == NULLUSOCK)
  84.         return;
  85.  
  86.     up->zout = (struct lzw *)mxallocw(sizeof(struct lzw));
  87.     up->zin = (struct lzw *)mxallocw(sizeof(struct lzw));
  88.     up->zout->codebits = LZWBITS;
  89.  
  90.     if(bits < LZWBITS)
  91.         up->zout->maxbits = LZWBITS;
  92.     else if(bits > 16 || bits == 0)
  93.         up->zout->maxbits = 16;
  94.     else if(bits >= LZWBITS && bits <= 16)
  95.         up->zout->maxbits = bits;
  96.     up->zout->nextbit = 0;
  97.     up->zout->prefix = -1;
  98.     up->zout->version = -1;
  99.     up->zout->code = -1;
  100.     up->zout->mode = (mode & 1);    /* only the last bit is significant */
  101.     up->zout->next = ZFLUSH + 1;    /* used only in LZWFAST mode */
  102.     up->zin->codebits = LZWBITS;
  103.     up->zin->maxbits = -1;
  104.     up->zin->nextbit = 0;
  105.     up->zin->prefix = -1;
  106.     up->zin->version = -1;
  107.     up->zin->code = -1;
  108.     up->zin->next = ZFLUSH + 1;
  109.     up->zin->mode = LZWCOMPACT;
  110.     up->zin->buf = NULLBUF;
  111. }
  112.  
  113. void
  114. lzwfree(up)
  115. struct usock *up;
  116. {
  117.     if(up->zout != NULLLZW) {
  118.         cleartbl(up->zout);
  119.         xfree((char *)up->zout);
  120.         up->zout = NULLLZW;
  121.     }
  122.     if(up->zin != NULLLZW) {
  123.         cleartbl(up->zin);
  124.         free_q(&up->zin->buf);
  125.         xfree((char *)up->zin);
  126.         up->zin = NULLLZW;
  127.     }
  128. }
  129. /* LZW encoding routine.
  130.  * See if the string specified by code + data is in the string table. If so,
  131.  * set prefix equal to the code of that string. Otherwise insert code + data
  132.  * in the string and set prefix equal to data.
  133.  */
  134. void
  135. lzwencode(s,data)
  136. int s;
  137. char data;
  138. {
  139.     struct usock *up;
  140.     struct lzw *lzw;
  141.     int32 code, pagelim;
  142.     unsigned int i,j;
  143.  
  144.     if((up = itop(s)) == NULLUSOCK)
  145.         return;
  146.  
  147.     lzw = up->zout;
  148.     code = up->zout->prefix;
  149.  
  150.     /* the first byte sent will be the version number */
  151.     if(lzw->version == -1) {
  152.         lzw->version = ZVERSION;
  153.         up->obuf->data[up->obuf->cnt++] = lzw->version;
  154.         /* then send our recommended maximum number of codebits */
  155.         up->obuf->data[up->obuf->cnt++] = lzw->maxbits;
  156.     }
  157.     lzw->cnt++;
  158.     if(code == -1) {
  159.         lzw->prefix = (int32) uchar(data);
  160.         return;
  161.     }
  162.     if(lzw->mode == LZWFAST) {
  163.         fastencode(up,data);
  164.         return;
  165.     }
  166.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  167.     if(code <= ZFLUSH)
  168.         i = j = 0;
  169.     else {
  170.         i = (unsigned int)((code - ZFLUSH) / LZWBLK);
  171.         j = (unsigned int)((code - ZFLUSH) % LZWBLK);
  172.     }
  173.     if(lzw->tu.tbl == (struct zentry **)0)
  174.         lzw->tu.tbl = (struct zentry **) cxallocw((unsigned)pagelim,
  175.             sizeof(struct zentry *));
  176.     for(;;) {
  177.         if(itop(s) == NULLUSOCK) /* the connection has been closed */
  178.             return;
  179.         if(up->zout == NULLLZW) /* ...or is about to be closed */
  180.             return;
  181.         if(lzw->tu.tbl[i] == (struct zentry *)0) {
  182.             lzw->tu.tbl[i] =
  183.                 (struct zentry *)cxallocw(LZWBLK,sizeof(struct zentry));
  184.             memset((char *)lzw->tu.tbl[i],0xff,LZWBLK * sizeof(struct zentry));
  185.         }
  186.         while(j < LZWBLK) {
  187.             if(lzw->tu.tbl[i][j].data == data &&
  188.                 lzw->tu.tbl[i][j].code == (int16) code) {
  189.                 lzw->prefix = (int32)(i * LZWBLK + j + ZFLUSH + 1);
  190.                 return;
  191.             }
  192.             if(lzw->tu.tbl[i][j].code == 0xffff) {
  193.                 lzw->tu.tbl[i][j].code = (int16) code;
  194.                 lzw->tu.tbl[i][j].data = data;
  195.                 addtobuffer(up,code);
  196.                 lzw->prefix = (int32) uchar(data);
  197.                 lzw->next++;
  198.                 if(lzw->next ==    (int32) (1 << lzw->codebits))
  199.                     /* the current table is now full */
  200.                     morebits(lzw);
  201.                 if(lzw->next + 1 == (int32) (1 << lzw->maxbits)) {
  202.                     /* The last codeword has been reached.
  203.                      * (Or last - 1.) Signal this and start all
  204.                      * over again.
  205.                      */
  206.                     addtobuffer(up,lzw->prefix);
  207.                     if(lzw->next + 1 == (int32) (1 << lzw->codebits))
  208.                         morebits(lzw);
  209.                     addtobuffer(up,ZCC);
  210.                     cleartbl(lzw);
  211.                 }
  212.                 return;
  213.             }
  214.             ++j;
  215.         }
  216.         pwait(NULL);
  217.         ++i;
  218.         j = 0;
  219.     }
  220. }
  221.  
  222. /* Used when LZWFAST mode is selected. Memory usage approx. (2^bits * 5)
  223.  * bytes.
  224.  */
  225. static void near
  226. fastencode(up,data)
  227. struct usock *up;
  228. char data;
  229. {
  230.     struct zfast *z;
  231.     struct mbuf *bp;
  232.     int16 cnt, h;
  233.     struct lzw *lzw = up->zout;
  234.     int32 code = up->zout->prefix;
  235.  
  236.     if(lzw->tu.bpp == NULLBUFP)
  237.         lzw->tu.bpp = (struct mbuf **) cxallocw(ZHASH,sizeof(struct mbuf *));
  238.  
  239.     h = lobyte(code);
  240.     h ^= hibyte(code);
  241.     h ^= data;
  242.     h = h % ZHASH;
  243.  
  244.     if(lzw->tu.bpp[h] == NULLBUF)
  245.         lzw->tu.bpp[h] = ambufw(LZWBLK);
  246.     bp = lzw->tu.bpp[h];
  247.     cnt = bp->cnt / sizeof(struct zfast);
  248.     z = (struct zfast *) bp->data;
  249.     while(cnt > 0) {
  250.         if(z->data == data && z->code == (int16) code) {
  251.             lzw->prefix = (int32) z->owncode;
  252.             return;
  253.         }
  254.         z++;
  255.         if(--cnt == 0) {
  256.             if(bp->next == NULLBUF)
  257.                 break;
  258.             bp = bp->next;
  259.             cnt = bp->cnt / sizeof(struct zfast);
  260.             z = (struct zfast *) bp->data;
  261.         }
  262.     }
  263.     if(bp->size - bp->cnt >= sizeof(struct zfast)) {
  264.         z = (struct zfast *) &bp->data[bp->cnt];
  265.         bp->cnt += sizeof(struct zfast);
  266.     }
  267.     else {
  268.         bp->next = ambufw(LZWBLK);
  269.         z = (struct zfast *) bp->next->data;
  270.         bp->next->cnt = sizeof(struct zfast);
  271.     }
  272.     z->code = (int16)code;
  273.     z->data = data;
  274.     z->owncode = (int16)lzw->next++;
  275.     addtobuffer(up,code);
  276.     lzw->prefix = (int32) uchar(data);
  277.     if(lzw->next == (int32) (1 << lzw->codebits)) {
  278.         /* Increase the number of bits per codeword */
  279.         morebits(lzw);
  280.     }
  281.     if(lzw->next + 1 == (int32) (1 << lzw->maxbits)) {
  282.         /* The last codeword has been reached. (Or last - 1.)
  283.          * Signal this and start all over again.
  284.          */
  285.         addtobuffer(up,lzw->prefix);
  286.         if(lzw->next + 1 == (int32) (1 << lzw->codebits))
  287.             morebits(lzw);
  288.         addtobuffer(up,ZCC);
  289.         cleartbl(lzw);
  290.     }
  291.     pwait(NULL);
  292. }
  293.  
  294. /* increase the number of significant bits in the codewords, and increase
  295.  * the size of the string table accordingly.
  296.  */
  297. static void near
  298. morebits(lzw)
  299. struct lzw *lzw;
  300. {
  301.     struct zentry **newt;
  302.     int32 pagelim, oldp = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  303.  
  304.     lzw->codebits++;
  305.  
  306.     if(lzw->mode != LZWFAST) {
  307.         pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  308.         newt = (struct zentry **) cxallocw((int)pagelim,sizeof(struct zentry *));
  309.         memcpy(newt,lzw->tu.tbl,sizeof(struct zentry *) * (int)oldp);
  310.         xfree((char *)lzw->tu.tbl);
  311.         lzw->tu.tbl = newt;
  312.     }
  313. }
  314.  
  315. static void near
  316. cleartbl(lzw)
  317. struct lzw *lzw;
  318. {
  319.     int32 pagelim,i;
  320.  
  321.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  322.     lzw->codebits = LZWBITS;
  323.     lzw->prefix = -1;
  324.     lzw->next = ZFLUSH + 1;
  325.     if(lzw->tu.p == NULL)
  326.         return;
  327.     if(lzw->mode == LZWCOMPACT) {
  328.         for(i=0; i < pagelim; ++i)
  329.             xfree((char *)lzw->tu.tbl[(int)i]);
  330.     } else {
  331.         for(i=0; i < ZHASH; ++i)
  332.             free_p(lzw->tu.bpp[(int)i]);
  333.     }
  334.     xfree((char *)lzw->tu.p);
  335.     lzw->tu.p = NULL;
  336. }
  337. /* Add a codeword to the code stream. Nextbit indicates at which bit in the
  338.  * code stream should be written first. The codeword ZFLUSH is used to
  339.  * pad the buffer to a byte boundary when the buffer will be flushed.
  340.  * The remaining bits of the ZFLUSH codeword are sent in the next buffer.
  341.  */
  342. static void near
  343. addtobuffer(up,code)
  344. struct usock *up;
  345. int32 code;
  346. {
  347.     if(up->zout->code != -1) {
  348.         /* Insert remaining bits of ZFLUSH codeword */
  349.         up->obuf->data[up->obuf->cnt] =
  350.              up->zout->code >> up->zout->flushbit;
  351.         if(up->zout->flushbit + 8 >= up->zout->codebits) { /* done */
  352.             up->zout->nextbit = (up->zout->codebits -
  353.                         up->zout->flushbit) % 8;
  354.             if(up->zout->nextbit == 0)
  355.                 ++up->obuf->cnt;
  356.             up->zout->code = -1;
  357.         }
  358.         else {
  359.             /* not done yet */
  360.             ++up->obuf->cnt;
  361.             up->zout->flushbit += 8;
  362.             addtobuffer(up,code);
  363.             return;
  364.         }
  365.     }
  366.     /* normal codewords are treated here */
  367.     if(up->zout->nextbit == 0) {
  368.         /* we are at a byte boundary */
  369.         if(code == ZFLUSH) {
  370.             up->zout->flushbit = 0;
  371.             up->zout->code = ZFLUSH;
  372.             return;
  373.         }
  374.         up->obuf->data[up->obuf->cnt++] = (char) code;
  375.     }
  376.     else
  377.         up->obuf->data[up->obuf->cnt++] |= code << up->zout->nextbit;
  378.     if(code == ZFLUSH) {
  379.         /* interrupt here and save the rest of the ZFLUSH
  380.          * codeword for later.
  381.          */
  382.         up->zout->flushbit = 8 - up->zout->nextbit;
  383.         up->zout->code = ZFLUSH;
  384.         return;
  385.     }
  386.     up->obuf->data[up->obuf->cnt] = code >> (8 - up->zout->nextbit);
  387.     /* start on a third byte if necessary */
  388.     if(16 - up->zout->nextbit < up->zout->codebits)
  389.         up->obuf->data[++up->obuf->cnt] = code >> (16 - up->zout->nextbit);
  390.     up->zout->nextbit = (up->zout->nextbit + up->zout->codebits) % 8;
  391.     if(up->zout->nextbit == 0)
  392.         ++up->obuf->cnt;
  393. }
  394.  
  395. void
  396. lzwflush(up)
  397. struct usock *up;
  398. {
  399.     /* interrupt the encoding process and send the prefix codeword */
  400.     if(up->zout->prefix != -1) {
  401.         addtobuffer(up,up->zout->prefix);
  402.         if(up->zout->next + 1 == (int32) (1 << up->zout->codebits))
  403.             morebits(up->zout);
  404.         up->zout->prefix = -1;
  405.     }
  406.     /* signal this by sending the ZFLUSH codeword */
  407.     addtobuffer(up,ZFLUSH);
  408. }
  409.  
  410. int
  411. lzwdecode(up)
  412. struct usock *up;
  413. {
  414.     int32 code,data;
  415.     if(up->zin->version == -1 && (up->zin->version = PULLCHAR(&up->ibuf)) == -1)
  416.         return -1;
  417.     if(up->zin->maxbits == -1) {
  418.         /* receive a recommended value for the maximum no of bits */
  419.         if((up->zin->maxbits = PULLCHAR(&up->ibuf)) == -1)
  420.             return -1;
  421.         if(up->zout->maxbits > up->zin->maxbits) {
  422.             if(up->zout->codebits > up->zin->maxbits) {
  423.                 /* We are already using more bits than our
  424.                  * peer want us to, so clear the encoding
  425.                  * table immediately.
  426.                  */
  427.                 addtobuffer(up,up->zout->prefix);
  428.                 if(up->zout->next + 1 == (int32) (1 << up->zout->codebits))
  429.                     morebits(up->zout);
  430.                 addtobuffer(up,ZCC);
  431.                 cleartbl(up->zout);
  432.             }
  433.             up->zout->maxbits = up->zin->maxbits;
  434.         }
  435.     }
  436.     for(;;) {
  437.         if((data = PULLCHAR(&up->zin->buf)) != -1)
  438.             return (int) data;
  439.         if((code = nextcode(up)) == -1)
  440.             return -1;
  441.         decodetbl(code,up->zin);
  442.         up->zin->cnt += len_p(up->zin->buf);
  443.         pwait(NULL);                /* TEST */
  444.     }
  445. }
  446.  
  447. static void near
  448. getstring(code,lzw)
  449. int32 code;
  450. struct lzw *lzw;
  451. {
  452.     int i, j;
  453.  
  454.     for(;;) {
  455.         if(code < ZFLUSH) {
  456.             lzw->buf = pushdown(lzw->buf,1);
  457.             *lzw->buf->data = uchar(code);
  458.             return;
  459.         }
  460.         i = (int)((code - ZFLUSH - 1) / LZWBLK);
  461.         j = (int)((code - ZFLUSH - 1) % LZWBLK);
  462.         lzw->buf = pushdown(lzw->buf,1);
  463.         *lzw->buf->data = lzw->tu.tbl[i][j].data;
  464.         code = (int32) lzw->tu.tbl[i][j].code;
  465.     }
  466. }
  467.  
  468. static char near
  469. firstchar(code,lzw)
  470. int32 code;
  471. struct lzw *lzw;
  472. {
  473.     int i, j;
  474.  
  475.     for(;;) {
  476.         if(code < ZFLUSH)
  477.             return uchar(code);
  478.         i = (int)((code - ZFLUSH - 1) / LZWBLK);
  479.         j = (int)((code - ZFLUSH - 1) % LZWBLK);
  480.         code = (int32) lzw->tu.tbl[i][j].code;
  481.     }
  482. }
  483.  
  484. static void near
  485. decodetbl(code,lzw)
  486. int32 code;
  487. struct lzw *lzw;
  488. {
  489.     unsigned int i,j;
  490.     int32 pagelim;
  491.  
  492.     if(code > lzw->next) {
  493.         tprintf("LZW protocol error, process %s\n",Curproc->name);
  494.         return;
  495.     }
  496.     if(lzw->buf == NULLBUF) {
  497.         lzw->buf = ambufw(512);
  498.         /* allow us to use pushdown() later */
  499.         lzw->buf->data += lzw->buf->size;
  500.     }
  501.     if(lzw->prefix == -1) {
  502.         getstring(code,lzw);
  503.         lzw->prefix = code;
  504.         return;
  505.     }
  506.     pagelim = ((int32) 1 << lzw->codebits) / LZWBLK + 1;
  507.     if(lzw->tu.tbl == (struct zentry **)0)
  508.         lzw->tu.tbl = (struct zentry **) cxallocw((unsigned)pagelim,
  509.                 sizeof(struct zentry *));
  510.     if(code < ZFLUSH)
  511.         goto intable;
  512.     i = (unsigned int)((code - ZFLUSH - 1) / LZWBLK);
  513.     j = (unsigned int)((code - ZFLUSH - 1) % LZWBLK);
  514.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  515.         lzw->tu.tbl[i] = (struct zentry *)
  516.                 cxallocw(LZWBLK,sizeof(struct zentry));
  517.         memset((char *)lzw->tu.tbl[i], 0xff,
  518.                 LZWBLK * sizeof(struct zentry));
  519.     }
  520.     if(lzw->tu.tbl[i][j].code == 0xffff) {
  521.         lzw->tu.tbl[i][j].data = firstchar(lzw->prefix,lzw);
  522.         lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  523.         getstring(code,lzw);
  524.         lzw->next = code + 1;
  525.         lzw->prefix = code;
  526.         if(lzw->next + 1 == (int32) (1 << lzw->codebits))
  527.             morebits(lzw);
  528.         return;
  529.     }
  530. intable:
  531.     getstring(code,lzw);
  532.     i = (unsigned int)((lzw->next - ZFLUSH - 1) / LZWBLK);
  533.     j = (unsigned int)((lzw->next - ZFLUSH - 1) % LZWBLK);
  534.     if(lzw->tu.tbl[i] == (struct zentry *)0) {
  535.         lzw->tu.tbl[i] = (struct zentry *)cxallocw(LZWBLK,sizeof(struct zentry));
  536.         memset((char *)lzw->tu.tbl[i], 0xff,LZWBLK * sizeof(struct zentry));
  537.     }
  538.     lzw->tu.tbl[i][j].data = firstchar(code,lzw);
  539.     lzw->tu.tbl[i][j].code = (int16) lzw->prefix;
  540.     lzw->next++;
  541.     lzw->prefix = code;
  542.     if(lzw->next + 1 == (int32)(1 << lzw->codebits))
  543.         morebits(lzw);
  544. }
  545.  
  546. /* extract the next codeword from the input stream */
  547. static int32 near
  548. nextcode(up)
  549. struct usock *up;
  550. {
  551.     int32 code;
  552.  
  553.     if(up->zin->code == -1) {    /* read the first character */
  554.         if((code = PULLCHAR(&up->ibuf)) == -1)
  555.             return -1;
  556.         up->zin->code = (code >> up->zin->nextbit);
  557.     }
  558.     if(up->ibuf == NULLBUF)        /* next byte is not available yet */
  559.         return -1;
  560.     /* continue assembling the codeword */
  561.     up->zin->code |= ((int32) uchar(*up->ibuf->data) <<
  562.             (8 - up->zin->nextbit)) & (((int32) 1 <<
  563.             up->zin->codebits) - 1);
  564.     if((16 - up->zin->nextbit) < up->zin->codebits) {
  565.         (void)PULLCHAR(&up->ibuf);
  566.         up->zin->nextbit -= 8; /* pull bits from a third byte */
  567.         return nextcode(up);
  568.     }
  569.     code = up->zin->code;
  570.     up->zin->code = -1;
  571.     up->zin->nextbit = (up->zin->nextbit + up->zin->codebits) % 8;
  572.     if(up->zin->nextbit == 0)
  573.         (void)PULLCHAR(&up->ibuf);
  574.     if(code == ZCC) {
  575.         cleartbl(up->zin);
  576.         return nextcode(up);
  577.     }
  578.     if(code == ZFLUSH) {
  579.         up->zin->prefix = -1;
  580.         return nextcode(up);
  581.     }
  582.     return code;
  583. }
  584.  
  585. #endif /* LZW */
  586.